1. Field of the Invention
The present invention relates to a video data encoder and method of encoding the video data, more particularly to a technique for raising the compression efficiency in intraframe coding for motion estimation with using discrete cosine transform.
2. Description of the Related Art
Video data encoding (coding) technology has been improved with wide industry participation, and various global standards for video data encoding for multimedia contents have been established. For example, H.263 is an international standard for video data encoding suitable for transmitting video data file, and MPEG (Moving Picture Experts Group) is another one suitable for storing video data files. Each of those techniques employs unique encoding algorithm(s) for appropriate bit rate suitable for the purpose.
For example, a coding technique employed in MPEG-4 being standardized internationally, is hybrid of two data coding techniques, discrete cosine transform (DCT) and estimation with motion compensation (MC). Those coding techniques work as a basic algorithm for video data coding in MPEG-4.
FIG. 6 is a block diagram for explaining typical encoding process in MPEG-4. There are two approaches for video data encoding: intraframe coding and interframe coding. The intraframe coding is a way to compress video data by referencing data in each frame, while the interframe coding refers differences between frames for compression.
The first step of the intraframe coding is to divide video object plane (VOD) into macroblocks by a divider 6a. A macroblock is a unit for intraframe coding process. FIG. 7 shows the structure of a macroblock. As shown in FIG. 7, a macroblock contains blocks of data from the luminance component (Y component) and from the chrominance components (Cb and Cr components). The structure shown in FIG. 7 is based on one of the chrominance formats called xe2x80x9c4:2:0 formatxe2x80x9d which includes four luminance blocks and two chrominance blocks. Each block is subjected to DCT by a discrete cosine transformer 6d, and thus transformed blocks are quantized by a quantizer 6e. Thus quantized data (DCT coefficient and amplitude) are subjected to variable-length coding by a variable-length coder 6f. Finally, resultant codes are output to be transmitted or the like. On the contrary, the quantized blocks are subjected to inverse quantization by an inverse quantizer 6g for restoring frame to be used as source frame for next estimation. Further, the DCT coefficient is subjected inverse DCT by an inverse discrete cosine transformer 6h. Thus restored VOP is transferred to a frame memory 6j via an addition circuit 6i. 
In interframe coding on the contrary, a motion detecting method such as block matching is carried out against a VOP adjoining to a VOP having target macroblock to detect estimative macroblock having least difference from the target macroblock by a motion vector detector 6b. A signal representing motion of the estimative macroblock having the least difference is called motion vector. And a frame to which referred for generating the estimative macroblock is called a reference VOP. The motion compensation is carried out against the reference VOP stored in a frame memory 6j based on the detected motion vector to obtain an appropriate estimative macroblock. A subtraction circuit 6c obtains difference between the target macroblock and the detected estimative macroblock. Thus obtained difference signal is subjected to DCT by the discrete cosine transformer 6d, and DCT coefficient is quantized by the quantizer 6e. The quantized DCT coefficient is subjected to variable-length coding by the variable-length coder 6f together with the motion vector and amplitude.
Details of DCT will now be described. The DCT is one of Fourier Transform. The DCT transforms 2 dimensional image into 2 dimensional frequency, and the frequencies are divided into conspicuous low frequency components and inconspicuous high frequency components. Moreover, it is able to obtain ubiquitous information. The following expression 1 represents 2D DCT on 8xc3x978 blocks, and expression 2 represents inverse DCT.                                                         F              ⁡                              (                                  u                  ,                  v                                )                                      =                                          (                                  1                  /                  4                                )                            ⁢                              C                ⁡                                  (                  u                  )                                            ⁢                              C                ⁡                                  (                  v                  )                                            ⁢                                                ∑                                      i                    =                    0                                    7                                ⁢                                                      ∑                                          j                      =                      0                                        7                                    ⁢                                                            f                      ⁡                                              (                                                  i                          ,                          j                                                )                                                              ⁢                                          cos                      ⁡                                              (                                                                              2                            ⁢                            i                                                    +                          1                                                )                                                              ⁢                    u                    ⁢                                          xe2x80x83                                        ⁢                                          π                      /                                                                                                    "AutoRightMatch"                ⁢        16        ⁢                  xe2x80x83                ⁢        cos        ⁢                  xe2x80x83                ⁢                  (                                    2              ⁢              j                        +            1                    )                ⁢        v        ⁢                  xe2x80x83                ⁢                  π          /          16                                    EXPRESSION        ⁢                  xe2x80x83                ⁢        1                                                                    f              ⁡                              (                                  u                  ,                  v                                )                                      =                                          (                                  1                  /                  4                                )                            ⁢                                                ∑                                      i                    =                    0                                    7                                ⁢                                                      ∑                                          j                      =                      0                                        7                                    ⁢                                                            C                      ⁡                                              (                        u                        )                                                              ⁢                                          C                      ⁡                                              (                        v                        )                                                              ⁢                                          F                      ⁡                                              (                                                  u                          ,                          v                                                )                                                              ⁢                                          cos                      ⁡                                              (                                                                              2                            ⁢                            i                                                    +                          1                                                )                                                              ⁢                    u                    ⁢                                          xe2x80x83                                        ⁢                                          π                      /                                                                                                    "AutoRightMatch"                ⁢                  "AutoLeftMatch"          "AutoRightMatch"                ⁢        16        ⁢                  xe2x80x83                ⁢        cos        ⁢                  xe2x80x83                ⁢                  (                                    2              ⁢              j                        +            1                    )                ⁢        v        ⁢                  xe2x80x83                ⁢                  π          /          16                                    EXPRESSION        ⁢                  xe2x80x83                ⁢        2            
where C(u)=1/{square root over (2)}(u=0)
C(u)=1 (uxe2x89xa00)
C(v)=1{square root over (2)}(v=0)
C(v)=1(vxe2x89xa00)
IDCT (i, j): pixel values
DCT (u, v): DCT coefficients
FIG. 8 is a diagram showing a target block X and its peripheral adjoining blocks A, B, and C. Each of squares in each block represents a DCT coefficient. DCT coefficients represented by left upper squares in the blocks are direct current (DC) components, while the others are alternating current (AC) components. MPEG-4 has an advantage over MPEG-2 because MPEG-4 realizes improved efficiency for coding intra-type blocks by adaptively coding both quantized DC and AC components with a predictive coding technique, while MPEG-2 features differential coding to be applied only to DC components in intra-type blocks.
A DCT coefficient memory 6k stores quantized DCT coefficients of the reference block (DC components, and AC components for a first horizontal row or a first vertical column) as predicted values. Of the predicted values, values for DC components are subjected to predictive coding and output, while it is determined whether predictive coding should be applied to the AC components or not (a prediction selector 6m).
In a case whether the predictive coding should be applied to the AC components, a switch SW1 is turned on, so that a subtraction circuit 61 calculates difference (prediction error) between the predicted values in the memory 6k and the quantized AC components and variable-length coding is carried out by the variable-length coder 6f. On the contrary, if the predictive coding is ineffective, the switch SW1 is turned off, so that the variable-length coding performed by the variable-length coder 6f is just applied to the quantized AC components.
An operation of the conventional intraframe coding will now be described.
FIG. 9 is a flowchart for explaining process flow of the conventional intraframe coding. In the following explanation, for example, X(i, j) represents DCT coefficient in the block X (wherein i represents vertical components, j represents horizontal components; i, j=0, 1, 2, . . . , 7).
Input video data (VOP) are divided into unit macroblocks. Each of the macroblocks are subjected to DCT to be quantized (step A1). Then, sum of absolute values S0 of the AC components of the DCT coefficients in the first vertical column of the first horizontal row is calculated (step A2). The following expression 3 represents the sum of the absolute values S0.
S0=xcexa3|X(i,0)| or xcexa3|X(0,j)|(i, j=1, 2, . . . , 7)xe2x80x83xe2x80x83EXPRESSION 3
Then, the sum total (xcexa3mS0) of the sums of absolute values S0 of the AC components for all blocks (Y, Cb, and Cr components) in the macroblocks is calculated, and the result is stored on a work area in a RAM 8.
Then, the DC components in the quntized DCT coefficients are coded by the prediction coding. Prediction values of the DC components are adaptively selected based on inclines between horizontal and vertical DC components among blocks around the target block.
The following expression 4 represents prediction value Xxe2x80x2 (0, 0) of the DC components in a block X. The memory 6k stores the determined prediction value Xxe2x80x2 (steps A3 to A5).
if (|A(0,0)xe2x88x92B(0,0)| less than |B(0,0)xe2x88x92C(0,0)|
then Xxe2x80x2(0,0)=C(0,0)
else Xxe2x80x2(0,0)=A(0,0)xe2x80x83xe2x80x83EXPRESSION 4
where A (0, 0): DC components in block A
B (0, 0): DC components in block B
C (0, 0): DC components in block C
X (0, 0): DC components in block X
In a case where the prediction value of the DC components is C (0, 0), the AC components X (0, j)(j=1, 2, . . . , 7; hatched portion HX in FIG. 8) for the first horizontal line in the target block X are coded by the prediction coding. In this case, the prediction value is the AC components C(0, j)(j=1, 2, . . . , 7; hatched portion HC in FIG. 8) for the first horizontal line in the block C, which is stored in the memory 6k. The following expression 7 represents prediction error (PE) in the AC components.
PE=X(0,j)xe2x88x92C(0,j)xe2x80x83xe2x80x83EXPRESSION 7
Since quantization scaling for the AC components among the blocks may be uneven sometimes as well as a case of the DC components, the prediction values are normalized.
In a case where the prediction error in the AC components is larger than unpredicted AC components, the unpredicted AC components are coded directly without prediction. The prediction selector 6m determines whether AC component prediction should be applied to each macroblock. The determination is carried out by comparing xcexa3mS0 (see expression 3) with xcexa3mS, that is, comparing the sum of absolute values of the unpredicted AC components (in first horizontal line or the first vertical column) of all blocks (Y, Cb, and Cr components) in the target block X with the sum of absolute values of the prediction errors in the AC components. The following expression 8 represents the sum S of absolute values of the prediction errors in the AC components in each block.
S=xcexa3|X(i,0)xe2x88x92A(i,0) or xcexa3|X(0,j)xe2x88x92C(0,j)|(i,j=1, 2, . . . , 7)xe2x80x83xe2x80x83EXPRESSION 8
For determining effectiveness of the AC component prediction, the sum total xcexa3mS over all blocks (Y, Cb, and Cr components) in the target block whose sum S of absolute values of prediction errors in the AC components is calculated (step A7), and the sum of absolute values of the prediction errors (xcexa3mS) is compared with the sum of absolute values in the unpredicted AC components (xcexa3mS0) (step A8). The comparison is carried out in accordance with the following expression 9.
xcexa3mS less than xcexa3mS0xe2x80x83xe2x80x83EXPRESSION 9
If the inequality expression 9 is satisfied (YES at step A8), the switch SW1 is turned on, thus the prediction coding is allowed, that is, the prediction errors in the AC components are subjected to variable-length coding (step A9). If the inequality expression 9 is not satisfied (NO at step A8), the switch SW1 is turned off, thus the prediction coding is not allowed, that is, the unpredicted AC components are subjected to the variable-length coding (step A10).
Accordingly, xcexa3mS (the sum of absolute values of prediction errors in the AC components) and xcexa3mS0 (the sum of absolute values of the AC components) are calculated and compared with each other to determine necessity of the AC component prediction through the conventional coding process.
Since the conventional technique requires the determination whether the prediction is effective or not, it is necessary to perform calculations to find outxcexa3mS (prediction errors in the AC components) over every macroblocks even if it is obvious that the prediction is ineffective in a case where the macroblocks have a few AC blocks, for example, the VOP represents the sky or the ground whose tone is almost uniform. Such the extra calculations causes redundancy in the coding process.
The present invention has been made in consideration of the above. It is an object of the present invention to provide a video data encoder and a method and a recording medium which realizes high speed efficient video data encoding in the prediction coding by which both DC components and AC components in DCT coefficients are adaptively predicted, with eliminating redundant tasks in prediction coding for AC components.
According to the present invention, a video data encoder which adaptively encodes both direct current components and alternating current components of discrete cosine transform coefficients in target blocks by prediction coding, comprises:
a determination unit which determines whether the prediction for the alternating current components in the target block is effective or not; and
an encoder which encodes the alternating current components without calculating prediction error in the alternating current components in the target blocks when said determination unit determines that the prediction is ineffective.
This structure realizes high speed efficient coding because of less calculation in coding when AC component prediction is obviously ineffective. More precisely, the encoder does not calculate prediction error in AC components in blocks which represents almost uniform images such as the sky or the ground.